9021. Количество чисел вида 2^x * 3^y

Найдите количество целых чисел на промежутке [a, b], представимых в виде 2^x * 3^y (x ≥ 0, y ≥ 0).

Вход. Содержит не более 10⁶ строк. Каждая строка содержит два целых числа a и b (0 ≤ a ≤ b ≤ 10¹⁸), задающих один запрос.

Выход. Для каждого запроса выведите в отдельной строке количество целых чисел на интервале [a, b] включительно, которые имеют вид 2^x * 3^y.

Пример входа	Пример выхода
1 10 100 200	7 5

РЕШЕНИЕ

бинарный поиск

Анализ алгоритма

Количество чисел вида 2^x * 3^y, не больших 10¹⁸, не так уж много. Сгенерируем их в массиве v.

Количество искомых чисел f(a, b) на отрезке [a, b] равно f(0, b) – f(0, a – 1). Запрос f(0, q) означает количество чисел вида 2^x * 3^y , не больших q. Ответ на него ищем при помощи бинарного поиска на массиве v.

Пример

Сгенерируем числа вида 2^x * 3^y , не больших 200.

Отрезку [1; 10] принадлежит 7 чисел (выделены синим).

Отрезку [100; 200] принадлежит 5 чисел (выделены зеленым).

Найдем решение для отрезка [10; 20]:

upper_bound(v.begin(), v.end(), 20) – upper_bound(v.begin(), v.end(), 9) = 3

Действительно, отрезку [10; 20] принадлежит 3 числа искомого вида:

12, 16, 18

Реализация алгоритма

Объявим константу MAX = 10¹⁸. Объявим рабочий массив v.

#define MAX 1000000000000000000LL

vector<long long> v;

Функция preprocess генерирует все числа вида 2^x * 3^y, не больших 10¹⁸, в массиве v. Для каждого значения x = 1, 2, 4, 8, … переберем y = 1, 3, 9, 27, … до тех пор пока x * y < MAX.

void preprocess()

{

long long x = 1, y = 1;

while (x < MAX)

{

while (x * y < MAX)

{

v.push_back(x * y);

y *= 3;

}

x *= 2;

y = 1;

}

Отсортируем числа.

sort(v.begin(), v.end());

}

Основная часть программы. Генерируем массив чисел вида 2^x * 3^y.

preprocess();

Читаем запрос – отрезок [a, b]. Количество искомых чисел f(a, b) на отрезке [a, b] равно f(0, b) – f(0, a – 1).

while (scanf("%lld %lld", &a, &b) == 2)

{

res = upper_bound(v.begin(), v.end(), b) - upper_bound(v.begin(),

v.end(), a - 1);

printf("%lld\n", res);

}